1. Field of Invention
This invention relates to address generation and in particular a high speed hardware address generation for a circular buffer.
2. Description of Related Art
Addresses for circular buffers can be modified by a positive or negative offset to determine the next address. The buffer has a finite length and when the upper or lower bound is reached the next address may need to be wrapped such as to start from the opposite boundary. This makes the buffer to appear to be circular.
In U.S. Pat. No. 5,623,621 (Garde) is a hardware circular buffer address generator utilizing an adder-subtractor and a second adder to adjust the next circular buffer address to be within a valid range. This address generator calculates both the absolute value and the wrapped value of the next address and selects one according to which one falls within the valid address range. The base address B is used for both the upper and lower bounds of the circular buffer, and it appears that the comparator requires equal to and less than, and equal to and greater than operations.
Referring to U.S. Pat. No. 5,659,698 (Weng et al.), a circular buffer address generator is described in which a potential next address is generated and compared with both the upper and lower boundaries of the circular buffer requiring two adders in the wrap-around generator. If the potential next address falls outside the valid range of the circular buffer, the beginning address and a wrap address is presented to a multiplexer for selection as the next address.
In U.S. Pat. No. 5,659,700 (Chen et al.) a method and apparatus is shown for generating an address for a circular buffer using a modulo address for accessing the buffer. This invention determines an absolute address and a wrapped address, and comparisons are made to determine which to use depending on the sign of the offset. Referring to U.S. Pat. No. 4,742,479, (Kloker) a modulo arithmetic unit is shown for providing a sum and difference of two numbers with each modulus having a lower and upper boundary with a range of intermediate values. In U.S. Pat. No. 4,169,289 (Shively) a circular buffer is shown as an apparatus for designating contiguous memory locations in a data memory. when a potential next address exceeds the upper buffer location, the buffer length is subtracted from the potential next address to produce an address within the buffer range.
This invention is a fast and efficient hardware implementation for address generator of a circular buffer. The hardware implementation involves two adders, a comparator and a multiplexer. One of the two adders is a three input adder in which the third input is masked to zero when only two inputs are needed. The operation of the address generating circuitry involves only addition, and there is no need at run time to determine any change in sign for any of the inputs to the circuitry.
The first of the two adders has three inputs to add together, the present address (A), an address offset (M) and the negative value of the length of the circular buffer (xe2x88x92L). The negative value of the length of the buffer is created by an exclusive NOR with the MSB (most significant bit) of the offset, and Is used to bring the potential new address back into range when a positive offset forces the potential new address beyond the upper bound of the circular buffer. When the offset is negative, the negative value of the buffer length is not needed and a mask of zero value Is used to inhibit the negative value of the buffer length from the three input adder. A residue of xe2x80x9c1xe2x80x9d is connected to the three input adder by using an Inverted output of MSB of the offset. When the offset is positive, MSB=0, and a residue of xe2x80x9c1xe2x80x9d is needed in conjunction with a negative value of the length of the circular buffer (xe2x88x92L).
The output of the three input adder is connected to an input of a two input adder, a multiplexer, and a comparator. The two input adder adds a positive value of the buffer length (L) to the sum of the three input adder. The output of the two input adder is connected to an input of the multiplexer. The multiplexer selects one of its two inputs as the next address for the circular buffer under the control of the comparator. The comparator compares the output of the three input adder to the base address (B) of the circular buffer. The results of the comparator is used to select which input to the multiplexer is the next address for the circular buffer, the output of the three input adder or the output of the two input adder.
The output opf the comparator (Cond.) selects the correct multiplexer input based on the comparison of the base address (B) and the output of the three input adder. When the offset is positive, the two input adder produces a sum which is A+M and the three input adder produces a sum A+Mxe2x88x92L. When the offset is negative, the two input adder produces a sum which is A+M+L and the three input adder A+M. Thus each adder produces a summation of different elements depending on the polarity of the offset. If the offset is negative and the base address (B) Is greater than the output of the three input adder (A+M), then the output of the two way adder (A+M+L) is chosen. If the offset is negative and the base address (B) is less than the output of the three input adder, then the output of the three way adder (A+M) is chosen. If the offset is positive and the base address (B) is greater than the output of the three input adder (A+Mxe2x88x92L), then the output of the two way adder (A+M) is chosen. If the offset Is positive and the base address (B) is less than the output of the three input adder, then the output of the three input adder (A+Mxe2x88x92L) is chosen.